package org.springside.modules.ds.trie;
/**
 * 适用于大数据量的搜索以完成自动补足效果的简单三叉树结构，
 * 如果是仅有几百条的数据不如用暴力搜索方式，已经足够快了
 * @author Saya
 *
 */
public class TernaryTree {

	private Node m_root = null;

	public Node getM_root() {
		return m_root;
	}

	public void setM_root(Node m_root) {
		this.m_root = m_root;
	}

	private void Add(String s, int pos, Node node) {
		if (node == null) {
			node = new Node(s.charAt(pos), false);
		}
		if (s.charAt(pos) < node.getM_char()) {
			Add(s, pos, node.getM_left());
		} else if (s.charAt(pos) > node.getM_char()) {
			Add(s, pos, node.getM_right());
		} else {
			if (pos + 1 == s.length()) {
				node.setM_wordEnd(true);
			} else {
				Add(s, pos + 1, node.getM_center());
			}
		}
	}

	public void Add(String s) {
		if (s == null || s == "") {
			throw new IllegalArgumentException();
		}
		Add(s, 0, getM_root());
	}

	public boolean Contains(String s) {
		if (s == null || s == "") {
			throw new IllegalArgumentException();
		}
		int pos = 0;
		Node node = getM_root();
		while (node != null) {
			// int cmp = s.charAt(pos) - node.getM_char();
			if (s.charAt(pos) < node.getM_char()) {
				node = node.getM_left();
			} else if (s.charAt(pos) > node.getM_char()) {
				node = node.getM_right();
			} else {
				if (++pos == s.length()) {
					return node.isM_wordEnd();
				}
				node = node.getM_center();
			}
		}
		return false;
	}

}
